//===----------------------------------------------------------------------===//
//
//                         CMU-DB Project (15-445/645)
//                         ***DO NO SHARE PUBLICLY***
//
// Identification: src/page/b_plus_tree_internal_page.cpp
//
// Copyright (c) 2018, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include <iostream>
#include <sstream>

#include "common/exception.h"
#include "storage/page/b_plus_tree_internal_page.h"

namespace bustub {
/*****************************************************************************
 * HELPER METHODS AND UTILITIES
 *****************************************************************************/
/*
 * Init method after creating a new internal page
 * Including set page type, set current size, and set max page size
 */
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::Init(int max_size) {
  SetPageType(IndexPageType::INTERNAL_PAGE);
  SetSize(0);
  SetMaxSize(max_size);
  SetMinSize((max_size + 1) / 2);
}
/*
 * Helper method to get/set the key associated with input "index"(a.k.a
 * array offset)
 */
INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::KeyAt(int index) const -> KeyType {
  // BUSTUB_ASSERT(index > 0, "index lt 0");
  return array_[index].first;
}

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::SetKeyAt(int index, const KeyType &key) {
  // BUSTUB_ASSERT(index > 0, "index lt 0");
  array_[index].first = key;
}

/*
 * Helper method to get the value associated with input "index"(a.k.a array
 * offset)
 */
INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::ValueAt(int index) const -> ValueType { return array_[index].second; }

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::GetArray() -> MappingType * { return array_; }

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::GetArray() const -> const MappingType * { return array_; }

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::LowerBound(const KeyType &key, const KeyComparator &cmp) -> int {
  int left = 0;
  int right = GetSize();
  while (left < right) {
    int mid = left + (right - left) / 2;  // 第一个大于等于T,查找，插入
    if (cmp(key, array_[mid].first) <= 0) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::UpperBound(const KeyType &key, const KeyComparator &cmp) const -> int {
  int left = 1;
  int right = GetSize();
  while (left < right) {
    int mid = left + (right - left) / 2;  // 第一个大于key
    if (cmp(key, array_[mid].first) < 0) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left - 1;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::BinarySearch(const KeyType &key, const KeyComparator &cmp) -> int {
  int left = 1;
  int right = GetSize() - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;  // 第一个大于等于T,查找，插入
    if (cmp(key, array_[mid].first) == 0) {
      return mid;
    }
    if (cmp(key, array_[mid].first) < 0) {
      right = mid - 1;
    }
    if (cmp(key, array_[mid].first) > 0) {
      left = mid + 1;
    }
  }
  return -1;
}

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::Insert(const KeyType &key, const ValueType &value, const KeyComparator &cmp) {
  // 内部结点从1下标开始?
  // array_[GetSize()] = MappingType(key, value);
  int size = GetSize();
  bool found = false;
  for (int i = size - 1; i >= 1; i--) {
    if (cmp(key, array_[i].first) < 0) {
      array_[i + 1] = array_[i];
    } else {
      array_[i + 1] = MappingType(key, value);
      found = true;
      break;
    }
  }
  if (!found && size == 0) {
    array_[0] = MappingType(key, value);
  }
  if (!found && size > 0) {
    array_[1] = MappingType(key, value);
  }
  IncreaseSize(1);
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::CopyArray(const MappingType *array, int start, int size, int dst_start) -> void {
  for (int i = 0; i < size; i++) {
    array_[i + dst_start] = array[start + i];
  }
  SetSize(size + dst_start);
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::ValueIndex(const ValueType &value) const -> int {
  int size = GetSize();
  for (int i = 0; i < size; i++) {
    if (value == array_[i].second) {
      return i;
    }
  }
  return -1;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::Remove(const KeyType &key, const KeyComparator &cmp) -> bool {
  int size = GetSize();
  bool found = false;
  for (int i = 0; i < size; i++) {
    if (cmp(key, array_[i].first) == 0) {
      found = true;
      for (int j = i; j < size - 1; j++) {
        array_[j] = array_[j + 1];
      }
      break;
    }
  }
  if (found) {
    IncreaseSize(-1);
  }
  return found;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::Remove(int index) -> MappingType {
  auto ret = array_[index];
  int size = GetSize();
  for (int j = index; j < size - 1; j++) {
    array_[j] = array_[j + 1];
  }
  IncreaseSize(-1);
  return ret;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::Insert(int index, const MappingType &kv) -> void {
  IncreaseSize(1);
  int size = GetSize();
  for (int j = size - 1; j > index; j--) {
    array_[j] = array_[j - 1];
  }
  array_[index] = kv;
}

// valuetype for internalNode should be page id_t
template class BPlusTreeInternalPage<GenericKey<4>, page_id_t, GenericComparator<4>>;
template class BPlusTreeInternalPage<GenericKey<8>, page_id_t, GenericComparator<8>>;
template class BPlusTreeInternalPage<GenericKey<16>, page_id_t, GenericComparator<16>>;
template class BPlusTreeInternalPage<GenericKey<32>, page_id_t, GenericComparator<32>>;
template class BPlusTreeInternalPage<GenericKey<64>, page_id_t, GenericComparator<64>>;
}  // namespace bustub
